﻿// Blocks POJ - 3734.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <cmath>
#include <algorithm>
 


using namespace std;

//https://vjudge.csgrandeur.cn/problem/POJ-3734

/*
熊猫接到了一项任务：画一条积木线。熊猫是个聪明的孩子，他开始思考涂色的数学问题。
假设一条线上有 N 块积木，每块积木可以涂成红色、蓝色、绿色或黄色。出于某种神秘的原因，熊猫希望红色积木和绿色积木的数量都是偶数。
在这种情况下，熊猫想知道有多少种不同的涂色方法。

输入
输入的第一行包含一个整数 T（1≤T≤100），即测试案例的数量。接下来的 T 行中，每一行都包含一个整数 N（1≤N≤10^9），表示块的数量。

输出
对于每个测试用例，输出在一行中绘制图块的方法数。由于答案可能很大，因此必须用 10007 对其进行模数化。

Sample Input
3
1
2
98877
Sample Output
2
6
*/




// memory limit
//const int N = 100000000;
//int dp[N][2][2];
//int t,n;
//
//void solve() {
//	cin >> n;
//
//	memset(dp, 0, sizeof dp);
//
//	dp[0][1][1] = 1;
//
//	for (int i = 1; i <= n; i++) {
//		//当前红绿都是偶数  可以 从以下状态转移 当前刷蓝色或者黄色。  当前刷 红色    当前刷 绿色
//		dp[i][1][1] =  (dp[i-1][1][1]+ dp[i - 1][1][1] + dp[i-1][1][0] +dp[i-1][0][1])%10007 ;
//		//当前红是偶数 绿色是奇数  可以从  当前蓝色或者黄色  当前刷红色
//		dp[i][1][0] = (dp[i - 1][1][0] + dp[i - 1][1][0] + dp[i - 1][0][0] + dp[i - 1][1][1]) % 10007;
//		dp[i][0][1] = (dp[i - 1][0][1] + dp[i - 1][0][1] + dp[i - 1][1][1] + dp[i - 1][0][0]) % 10007;
//		dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][0][0] + dp[i - 1][1][0] + dp[i - 1][0][1]) % 10007;
//	}
//
//	cout << dp[n][1][1] << endl;
//}
//
//
//int main()
//{
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//
//
//	return 0;
//}




const int MOD = 10007;
struct MATRIX {
	int a[3][3];
}A,B;

MATRIX operator * (const MATRIX& a, const MATRIX& b) {
	MATRIX C;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			C.a[i][j] = 0;
			for (int k = 0; k < 3; k++) {
				C.a[i][j] = (C.a[i][j] % MOD + ((a.a[i][k] % MOD) * (b.a[k][j]) % MOD) % MOD) % MOD;
			}
		}
	}

	return C;
}

MATRIX pow(MATRIX a, int x) {
	MATRIX C;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i == j) C.a[i][j] = 1;
			else C.a[i][j] = 0;
		}
	}

	while (x) {
		if (x & 1) C = C * a;
		a = a * a;
		x >>= 1;
	}

	return C;
}

int main() {
	int T, n;
	scanf("%d",&T);
	while (T--) {
		scanf("%d", &n);
		A.a[0][0] = 2, A.a[0][1] = 1, A.a[0][2] = 0;
		A.a[1][0] = 2, A.a[1][1] = 2, A.a[1][2] = 2;
		A.a[2][0] = 0, A.a[2][1] = 1, A.a[2][2] = 2;
		B.a[0][0] = 1, B.a[1][0] = 0, B.a[2][0] = 0;
		A = pow(A, n);
		A = A * B;

		printf("%d\n",A.a[0][0]%MOD);
	}

}